package com.example.designpatterns.strategy.sorting;

import com.example.designpatterns.strategy.Strategy;
import java.util.Arrays;

/**
 * 快速排序策略 - 使用快速排序算法实现排序
 */
public class QuickSortStrategy implements Strategy<int[], int[]> {
    
    @Override
    public int[] execute(int[] input) {
        if (input == null || input.length <= 1) {
            return input;
        }
        
        // 创建数组副本，不修改原始数据
        int[] array = Arrays.copyOf(input, input.length);
        
        // 执行快速排序
        quickSort(array, 0, array.length - 1);
        
        return array;
    }
    
    /**
     * 快速排序递归实现
     * @param array 待排序数组
     * @param low 低位索引
     * @param high 高位索引
     */
    private void quickSort(int[] array, int low, int high) {
        if (low < high) {
            // 获取分区点
            int pivotIndex = partition(array, low, high);
            
            // 递归排序左侧和右侧
            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }
    
    /**
     * 分区方法，返回分区点位置
     * @param array 待分区数组
     * @param low 低位索引
     * @param high 高位索引
     * @return 分区点索引
     */
    private int partition(int[] array, int low, int high) {
        // 选择最高位为基准值
        int pivot = array[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                
                // 交换元素
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        
        // 将基准值放到正确位置
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        
        return i + 1;
    }
} 